package com.explorati.LeetCode290.wordpattern;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 290. Word Pattern map + set (30分钟)
 * 
 * Given a pattern and a string str, find if str follows the same pattern.
 * 
 * Input: pattern = "abba", str = "dog cat cat dog" Output: true
 * 
 * @author explorati
 *
 */
public class Solution1 {
	public boolean wordPattern(String pattern, String str) {
		String[] s = str.split(" ");
		// 用Map存储每个字符对应的标志
		Map<Character, Integer> map = new HashMap<>();
		// 如果pattern和str的子字符串个数不等，直接返回false
		if (pattern.length() != s.length) {
			return false;
		}
		// 遍历s
		for (int i = 0; i < s.length; i++) {
			// 如果map中不包含pattern[i]，将pattern及其对应位置放入其中
			if (!map.containsKey(pattern.charAt(i))) {
				map.put(pattern.charAt(i), i);
			} else {
				// 如果map中已经有了pattern[i]，则对比当前pattern对应的String和pattern中存储的String，若不等，则返回false
				if (!s[map.get(pattern.charAt(i))].equals(s[i])) {
					return false;
				}
			}
		}
		// Set记录s的不同元素的个数
		Set<String> set = new HashSet<>();
		for (String i : s) {
			set.add(i);
		}
		// 去除 'aaaa' 'dog cat cat dog'的情况
		// 将map中的元素(即pattern的种类)和set中的元素(s的种类)进行对比，若不等，则为false
		if (set.size() != map.size()) {
			return false;
		}
		return true;
	}
}
